package org.niu.listnode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class MergeKLists {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for(ListNode head:lists){
            while(head!=null){
                q.add(head);
                head=head.next;
            }
        }
        ListNode ans = new ListNode(-1);
        ListNode tail = ans;
        while(!q.isEmpty()){
            ListNode poll = q.poll();
            tail.next = poll;
            tail = tail.next;
        }
        return ans.next;
    }
}
